//给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 
//
//
// 返回滑动窗口中的最大值。 
//
// 
//
// 进阶： 
//
// 你能在线性时间复杂度内解决此题吗？ 
//
// 
//
// 示例: 
//
// 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
//输出: [3,3,5,5,6,7] 
//解释: 
//
//  滑动窗口的位置                最大值
//---------------               -----
//[1  3  -1] -3  5  3  6  7       3
// 1 [3  -1  -3] 5  3  6  7       3
// 1  3 [-1  -3  5] 3  6  7       5
// 1  3  -1 [-3  5  3] 6  7       5
// 1  3  -1  -3 [5  3  6] 7       6
// 1  3  -1  -3  5 [3  6  7]      7 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10^5 
// -10^4 <= nums[i] <= 10^4 
// 1 <= k <= nums.length 
// 
// Related Topics 堆 Sliding Window


package leetcode.d_200_299;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

//Java：滑动窗口最大值
public class P239SlidingWindowMaximum{
    public static void main(String[] args) {
        Solution solution = new P239SlidingWindowMaximum().new Solution();
        LinkedList<Integer> window = new LinkedList<>();
        window.add(1);
        window.add(2);
        System.out.println(window.getFirst());
        // TO TEST
        System.out.println(solution.maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] maxSlidingWindow2(int[] nums, int k) {
            int n = nums.length;
            int[] res = new int[n-k+1];
            int idx = 0;
            LinkedList<Integer> window = new LinkedList<>();
            for (int i=0; i<n; i++) {
                if (i >= k && window.getFirst() <= i-k) {
                    // 移除队首元素
                    window.removeFirst();
                }
                while (!window.isEmpty() && nums[i] > nums[window.getLast()]) {
                    // 移除队尾比当前元素小的元素
                    window.removeLast();
                }
                window.add(i);
                if (i >= k-1) {
                    res[idx++] = nums[window.getFirst()];
                }
            }
            return res;
        }

        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums.length == 0 || k == 0) {
                return new int[0];
            }
            Deque<Integer> deque = new LinkedList<>();
            int[] res = new int[nums.length - k + 1];
            for (int idx = 0; idx < nums.length; idx++) {
                if (idx >= k && deque.peekFirst() <= idx-k) {
                    // 移除队首元素
                    deque.pollFirst();
                }
                if (!deque.isEmpty() && nums[idx] > nums[deque.peekLast()]) {
                    // 移除队尾元素
                    deque.pollLast();
                }
                deque.offer(idx);

                if (idx >= k-1) {
                    res[idx-k+1] = nums[deque.peekFirst()];
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}